W3. Predicates, Quantifiers, and De Morgan’s Laws

Author

Zakhar Podyakov

Published

September 18, 2025

Quiz | Flashcards

1. Summary

1.1 From Propositions to Predicates

In logic, a proposition is a declarative statement that is definitively either true or false, but not both. For instance, “The number 4 is an even number” is a true proposition. However, we often need to work with statements whose truth value depends on a variable, such as “x is an even number.”

This is where predicates come in. A predicate is a statement containing one or more variables, which becomes a proposition once the variables are replaced with specific values. We can represent the predicate “x is an even number” as \(P(x)\). When we set \(x=4\), \(P(4)\) becomes the true proposition “4 is an even number.” The set of all possible values a variable can take is called the domain. The truth of a predicate statement critically depends on its domain.

1.2 Quantifiers: Generalizing Predicates

Quantifiers are symbols that allow us to make general claims about the truth of a predicate over its entire domain, without having to test every single value. There are two primary quantifiers.

1.2.1 The Universal Quantifier (\(\forall\))

The universal quantifier, denoted by the symbol \(\forall\), stands for “for all” or “for any.” The statement \(\forall x P(x)\) asserts that the predicate \(P(x)\) is true for every single element \(x\) in the domain.

  • Example: If the domain is the set of all even numbers, the statement \(\forall x (\text{"x is divisible by 2"})\) is true.
  • Connection to Logic: For a finite domain \(\{x_1, x_2, \dots, x_n\}\), the universal statement \(\forall x P(x)\) is logically equivalent to the conjunction (AND) of the predicate for each element: \(P(x_1) \land P(x_2) \land \dots \land P(x_n)\). A universal statement is only true if all parts are true.
1.2.2 The Existential Quantifier (\(\exists\))

The existential quantifier, denoted by the symbol \(\exists\), stands for “there exists” or “for some.” The statement \(\exists x P(x)\) asserts that there is at least one element \(x\) in the domain for which the predicate \(P(x)\) is true.

  • Example: If the domain is the set of all integers, the statement \(\exists x (x^2 = 9)\) is true, because we can find at least one value (namely, 3 or -3) that makes it true.
  • Connection to Logic: For a finite domain \(\{x_1, x_2, \dots, x_n\}\), the existential statement \(\exists x P(x)\) is logically equivalent to the disjunction (OR) of the predicate for each element: \(P(x_1) \lor P(x_2) \lor \dots \lor P(x_n)\). An existential statement is true if at least one part is true.
1.3 Free and Bound Variables

In a logical formula, a variable can be either bound or free.

  • A variable is bound if it is within the scope of a quantifier. In the expression \(\forall x (x > y)\), the variable \(x\) is bound by the universal quantifier.
  • A variable is free if it is not bound by any quantifier. In the same expression, \(\forall x (x > y)\), the variable \(y\) is free.

A formula with no free variables is a proposition; its truth value can be determined (given a domain). A formula with free variables is a predicate; its truth value depends on the values assigned to the free variables.

1.4 Interpretation and Counterexamples
  • An interpretation is an assignment of a specific domain and meanings to the predicates in a formula that makes the formula TRUE.
  • A counterexample is an interpretation that makes the formula FALSE. Finding even a single case in the domain that violates a universal statement serves as a counterexample. For instance, to disprove \(\forall x (\text{"x is an odd number"})\) for the domain of integers, we only need to provide one counterexample, like the number 2, which is an integer but not odd.
1.5 De Morgan’s Laws for Quantifiers

De Morgan’s Laws provide a crucial relationship between negation and quantifiers, allowing us to move the negation symbol (\(¬\)) inside a quantifier by flipping the quantifier.

  1. Negating a Universal Quantifier: The negation of “for all x, P(x) is true” is “there exists an x for which P(x) is false.” \[ \neg \forall x P(x) \equiv \exists x \neg P(x) \] Analogy: To disprove the claim “All students passed the exam,” you only need to find one student who did not pass.
  2. Negating an Existential Quantifier: The negation of “there exists an x for which P(x) is true” is “for all x, P(x) is false.” \[ \neg \exists x P(x) \equiv \forall x \neg P(x) \] Analogy: To disprove the claim “There is a dragon in the castle,” you must check every room and confirm that all of them are dragon-free.
1.6 Properties of Quantifiers

Quantifiers interact with logical connectives like AND (\(&\)) and OR (\(∨\)) in specific ways.

  • Universal Quantifier and AND: A universal quantifier can be distributed over \(&\). The statement “all x have property P and property R” is the same as “all x have property P” AND “all x have property R”. \[ \forall x (P(x) \land R(x)) \equiv \forall x P(x) \land \forall x R(x) \]
  • Existential Quantifier and OR: An existential quantifier can be distributed over \(∨\). The statement “there is an x that has property P or property R” is the same as “there is an x with property P” OR “there is an x with property R”. \[ \exists x (P(x) \lor R(x)) \equiv \exists x P(x) \lor \exists x R(x) \]
  • Important Note: A universal quantifier cannot be distributed over \(∨\), and an existential quantifier cannot be distributed over \(&\).
1.7 Nested Quantifiers

Nested quantifiers occur when one quantifier is within the scope of another, such as \(\forall x \exists y (x+y=0)\). The order of quantifiers is critical.

  • Same Quantifiers: If the quantifiers are the same, their order does not matter. \[ \forall x \forall y P(x, y) \equiv \forall y \forall x P(x, y) \] \[ \exists x \exists y P(x, y) \equiv \exists y \exists x P(x, y) \]

  • Mixed Quantifiers: If the quantifiers are different, their order does matter and can completely change the meaning of the statement. \[ \exists x \forall y P(x, y) \rightarrow \forall y \exists x P(x, y) \] The statement on the left implies the one on the right, but the reverse is not true. Let’s analyze \(\exists x \forall y\) versus \(\forall y \exists x\):

    • \(\exists x \forall y P(x,y)\): “There exists a single \(x\) that works for all \(y\).” This is a very strong claim. For example, if \(P(x,y)\) is “\(x \geq y\)” in the domain of natural numbers, this is false. There is no single natural number that is greater than or equal to all other natural numbers.
    • \(\forall y \exists x P(x,y)\): “For any given \(y\), we can find some \(x\) that works.” The choice of \(x\) can depend on \(y\). For the same example, “\(x \geq y\)”, this is true. For any natural number \(y\), we can always find an \(x\) (e.g., \(x=y\) or \(x=y+1\)) that is greater than or equal to it.
1.8 Special Quantifiers

For convenience, we use extensions of the standard quantifiers.

  • Uniqueness Quantifier (\(\exists!\)): The statement \(\exists!x P(x)\) means “there exists a unique (one and only one) x such that \(P(x)\) is true.”
  • Restricted Quantifiers: We often restrict the domain of a quantifier to a certain condition.
    • Restricted Universal: \(\forall x > 0, P(x)\) means “for all x that are greater than 0, \(P(x)\) is true.” This is formally written as an implication: \[ \forall x (x > 0 \rightarrow P(x)) \]
    • Restricted Existential: \(\exists x > 0, P(x)\) means “there exists an x greater than 0 such that \(P(x)\) is true.” This is formally written as a conjunction: \[ \exists x (x > 0 \land P(x)) \]

2. Definitions

  • Set: An unordered collection of distinct elements.
  • Proposition: A declarative sentence that is unambiguously true or false.
  • Predicate: A sentence containing variables that becomes a proposition when the variables are assigned specific values from a domain.
  • Domain: The set of all possible values that a variable in a predicate can assume.
  • Universal Quantifier (\(\forall\)): A logical symbol meaning “for all” or “for every,” asserting that a predicate is true for all elements in the domain.
  • Existential Quantifier (\(\exists\)): A logical symbol meaning “there exists” or “for some,” asserting that a predicate is true for at least one element in the domain.
  • Bound Variable: A variable that falls within the scope of a quantifier.
  • Free Variable: A variable in a logical formula that is not bound by a quantifier.
  • Interpretation: An assignment of a domain and meanings to predicates that makes a formula TRUE.
  • Counterexample: An assignment of a domain and meanings to predicates that makes a formula FALSE.

3. Formulas

  • De Morgan’s Law for Universal Quantifier: \(\neg \forall x P(x) \equiv \exists x \neg P(x)\)
  • De Morgan’s Law for Existential Quantifier: \(\neg \exists x P(x) \equiv \forall x \neg P(x)\)
  • Restricted Universal: \(∀x∈A P(x) ≡ ∀x (A(x) → P(x))\)
  • Restricted Existential: \(∃x∈A P(x) ≡ ∃x (A(x) ∧ P(x))\)

4. Examples

4.1. Translate a Predicate Logic Statement (Lab 3, Task 1)

Let P(x) be “x has visited Innopolis”, where the domain consists of all students. Translate the statement ¬∀xP(x) into English.

Click to see the solution
  1. Identify the main operator: The statement is a negation (¬) of a universally quantified statement.
  2. Translate the quantifier and predicate: The expression ∀xP(x) translates to “All students have visited Innopolis.”
  3. Apply the negation: The negation “¬” means “It is not the case that…”.
  4. Combine and rephrase: “It is not the case that all students have visited Innopolis.” This is equivalent to saying that some students have not visited Innopolis.
Answer: A natural translation is: “Not every student has visited Innopolis.”
4.2. Translate a Predicate Logic Statement (Lab 3, Task 1.a)

Let P(x) be “x likes orange”, where the domain consists of all people. Translate ¬∃xP(x) into English.

Click to see the solution
  1. Identify the main operator: The statement is a negation (¬) of an existentially quantified statement.
  2. Translate the quantifier and predicate: The expression ∃xP(x) translates to “There exists a person who likes orange” or “Some person likes orange.”
  3. Apply the negation: “It is not the case that some person likes orange.”
  4. Find an equivalent statement: This is logically equivalent to saying that for all people, they do not like orange (∀x¬P(x)).
Answer: A natural translation is: “No person likes orange.”
4.3. Translate a Predicate Logic Statement (Lab 3, Task 1.b)

Let R(x) be “x knows C++”, where the domain consists of all people. Translate ∀x¬R(x) into English.

Click to see the solution
  1. Identify the quantifier: ∀x means “For every person x…”.
  2. Identify the predicate: ¬R(x) means “x does not know C++”.
  3. Combine the parts: “For every person x, x does not know C++.”
Answer: A more natural translation is: “No person knows C++.” or “Everyone does not know C++.”
4.4. Translate a Predicate Logic Statement (Lab 3, Task 1.c)

Let P(x) be “x likes orange” and R(x) be “x knows C++”, where the domain consists of all people. Translate ∀x(P(x) → R(x)) into English.

Click to see the solution
  1. Identify the quantifier: ∀x means “For every person x…”.
  2. Identify the logical structure: The structure is an implication (P(x) → R(x)), which means “If P(x), then R(x)”.
  3. Combine the parts: “For every person x, if x likes orange, then x knows C++.”
Answer: A natural translation is: “Every person who likes orange knows C++.”
4.5. Translate a Predicate Logic Statement (Lab 3, Task 1.d)

Let P(x) be “x likes orange” and R(x) be “x knows C++”, where the domain consists of all people. Translate ∀x(P(x) ∧ R(x)) into English.

Click to see the solution
  1. Identify the quantifier: ∀x means “For every person x…”.
  2. Identify the logical structure: The structure is a conjunction (P(x) ∧ R(x)), which means “P(x) and R(x)”.
  3. Combine the parts: “For every person x, x likes orange and x knows C++.”
Answer: The translation is: “Every person likes orange and knows C++.”
4.6. Translate a Predicate Logic Statement (Lab 3, Task 1.e)

Let P(x) be “x likes orange” and R(x) be “x knows C++”, where the domain consists of all people. Translate ∃x(P(x) ∨ R(x)) into English.

Click to see the solution
  1. Identify the quantifier: ∃x means “There exists a person x such that…”.
  2. Identify the logical structure: The structure is a disjunction (P(x) ∨ R(x)), which means “P(x) or R(x)”.
  3. Combine the parts: “There exists a person x such that x likes orange or x knows C++.”
Answer: The translation is: “There is a person who likes orange or knows C++.”
4.7. Translate a Predicate Logic Statement (Lab 3, Task 1.f)

Let P(x) be “x likes orange” and R(x) be “x knows C++”, where the domain consists of all people. Translate ∃x(P(x) ∧ R(x)) into English.

Click to see the solution
  1. Identify the quantifier: ∃x means “There exists a person x such that…”.
  2. Identify the logical structure: The structure is a conjunction (P(x) ∧ R(x)), which means “P(x) and R(x)”.
  3. Combine the parts: “There exists a person x such that x likes orange and x knows C++.”
Answer: The translation is: “There is a person who likes orange and also knows C++.”
4.8. Determine the Truth Value (Lab 3, Task 2)

Determine the truth value of the statement ∃x(x = 0) if the domain consists of all real numbers.

Click to see the solution
  1. Translate the statement: “There exists a real number x such that x is equal to 0.”
  2. Analyze the statement: The question asks if the number 0 is a member of the set of real numbers.
  3. Conclusion: The number 0 is a real number. Therefore, a value of x exists that satisfies the condition.
Answer: The statement is True.
4.9. Determine the Truth Value (Lab 3, Task 2.a)

Determine the truth value of the statement ∃x(x³ = -1) if the domain consists of all real numbers.

Click to see the solution
  1. Translate the statement: “There exists a real number x such that x cubed is -1.”
  2. Analyze the statement: We need to find if there is a real number solution to the equation x³ = -1.
  3. Find a value: The real number x = -1 is a solution, since (-1)³ = -1.
  4. Conclusion: Since we found an x in the domain that satisfies the condition, the statement is true.
Answer: The statement is True.
4.10. Determine the Truth Value (Lab 3, Task 2.b)

Determine the truth value of the statement ∀x(x = -x) if the domain consists of all real numbers.

Click to see the solution
  1. Translate the statement: “For every real number x, x is equal to its own negative.”
  2. Analyze the statement: The universal quantifier “∀” requires the condition to be true for all elements in the domain. We can test this by looking for a counterexample.
  3. Find a counterexample: Let x = 1. The equation becomes 1 = -1, which is false.
  4. Conclusion: Since we found a real number for which the condition is false, the statement is false.
Answer: The statement is False.
4.11. Determine the Truth Value (Lab 3, Task 2.c)

Determine the truth value of the statement ∃x∀y(x > y) if the domain consists of all real numbers.

Click to see the solution
  1. Translate the statement: “There exists a real number x such that for all real numbers y, x is greater than y.”
  2. Analyze the statement: This claims that there is a single real number that is greater than every real number.
  3. Find a counterexample: Assume such an x exists. Let’s choose any y. According to the statement, x > y should be true. But we can always choose a new value for y, for instance y = x + 1. In this case, x > x + 1 is false.
  4. Conclusion: No single real number x can be greater than all real numbers. Therefore, the statement is false.
Answer: The statement is False.
4.12. Determine the Truth Value (Lab 3, Task 2.d)

Determine the truth value of the statement ∀x∃y(x + y = 0) if the domain consists of all real numbers.

Click to see the solution
  1. Translate the statement: “For every real number x, there exists a real number y such that their sum is 0.”
  2. Analyze the statement: This statement claims that every real number has an additive inverse that is also a real number.
  3. Verify the condition: For any given real number x, we can choose y = -x. The sum is x + (-x) = 0. Since -x is always a real number if x is a real number, such a y always exists.
  4. Conclusion: The condition holds for all x in the domain.
Answer: The statement is True.
4.13. Rewrite a Negated Statement (Lab 3, Task 3.a)

Rewrite the statement ¬∃x(x ≥ 0) so that no negation is outside a quantifier.

Click to see the solution
  1. Apply the negation rule for quantifiers: The rule is ¬∃x P(x) ≡ ∀x ¬P(x).
  2. Apply the rule to the statement: ¬∃x(x ≥ 0) becomes ∀x ¬(x ≥ 0).
  3. Simplify the inner predicate: The negation of “greater than or equal to” (≥) is “less than” (<).
Answer: The rewritten statement is ∀x(x < 0).
4.14. Rewrite a Negated Statement (Lab 3, Task 3.b)

Rewrite the statement ¬∀x(¬P(x) ∨ R(x)) so that no negation is outside a quantifier or logical connective.

Click to see the solution
  1. Apply negation to the quantifier: The rule ¬∀x Q(x) ≡ ∃x ¬Q(x) transforms the statement to ∃x ¬(¬P(x) ∨ R(x)).
  2. Apply De Morgan’s Law: The rule ¬(A ∨ B) ≡ (¬A ∧ ¬B) transforms the inner part to ∃x (¬(¬P(x)) ∧ ¬R(x)).
  3. Apply the double negation law: The term ¬(¬P(x)) simplifies to P(x).
Answer: The rewritten statement is ∃x(P(x) ∧ ¬R(x)).
4.15. Rewrite a Negated Statement (Lab 3, Task 3.c)

Rewrite ¬∀x((x > 0) ∨ (x < 0)) so that no negation is outside a quantifier or logical connective.

Click to see the solution
  1. Apply negation to the quantifier: The statement becomes ∃x ¬((x > 0) ∨ (x < 0)).
  2. Apply De Morgan’s Law: The expression becomes ∃x (¬(x > 0) ∧ ¬(x < 0)).
  3. Simplify the predicates: ¬(x > 0) is (x ≤ 0), and ¬(x < 0) is (x ≥ 0).
  4. Combine the simplified predicates: The statement is now ∃x((x ≤ 0) ∧ (x ≥ 0)). This is only true when x = 0.
Answer: The rewritten statement is ∃x((x ≤ 0) ∧ (x ≥ 0)), which is equivalent to ∃x(x = 0).
4.16. Rewrite a Negated Statement (Lab 3, Task 3.d)

Rewrite ¬∃x∃yP(x, y) so that no negation is outside a quantifier.

Click to see the solution
  1. Apply negation to the first quantifier: The statement becomes ∀x ¬(∃yP(x, y)).
  2. Apply negation to the second quantifier: The statement becomes ∀x (∀y ¬P(x, y)).
Answer: The rewritten statement is ∀x∀y¬P(x, y).
4.17. Rewrite a Negated Statement (Lab 3, Task 3.e)

Rewrite ¬∀x∃y((x ≥ 0) ∧ (y < 0)) so that no negation is outside a quantifier or logical connective.

Click to see the solution
  1. Apply negation to the first quantifier: The statement becomes ∃x ¬(∃y((x ≥ 0) ∧ (y < 0))).
  2. Apply negation to the second quantifier: The statement becomes ∃x ∀y ¬((x ≥ 0) ∧ (y < 0)).
  3. Apply De Morgan’s Law: The statement becomes ∃x ∀y (¬(x ≥ 0) ∨ ¬(y < 0)).
  4. Simplify the predicates: The statement becomes ∃x ∀y ((x < 0) ∨ (y ≥ 0)).
Answer: The rewritten statement is ∃x∀y((x < 0) ∨ (y ≥ 0)).
4.18. Rewrite a Negated Statement (Lab 3, Task 3.f)

Rewrite ¬∃y(R(y) ∧ ∀x¬P(x, y)) so that no negation is outside a quantifier or logical connective.

Click to see the solution
  1. Apply negation to the outer quantifier: The statement becomes ∀y ¬(R(y) ∧ ∀x¬P(x, y)).
  2. Apply De Morgan’s Law: The statement becomes ∀y (¬R(y) ∨ ¬(∀x¬P(x, y))).
  3. Apply negation to the inner quantifier: The statement becomes ∀y (¬R(y) ∨ ∃x¬(¬P(x, y))).
  4. Apply the double negation law: The statement becomes ∀y (¬R(y) ∨ ∃xP(x, y)).
Answer: The rewritten statement is ∀y(¬R(y) ∨ ∃xP(x, y)).
4.19. Rewrite a Negated Statement (Lab 3, Task 3.g)

Rewrite ¬∃y(∃xS(x, y) ∨ ∀yT(x, y)) so that no negation is outside a quantifier or logical connective.

Click to see the solution
  1. Apply negation to the outer quantifier: The statement becomes ∀y ¬(∃xS(x, y) ∨ ∀yT(x, y)).
  2. Apply De Morgan’s Law: The statement becomes ∀y (¬(∃xS(x, y)) ∧ ¬(∀yT(x, y))).
  3. Apply negation to the inner quantifiers: The statement becomes ∀y (∀x¬S(x, y) ∧ ∃y¬T(x, y)).
Answer: The rewritten statement is ∀y(∀x¬S(x, y) ∧ ∃y¬T(x, y)).
4.20. Rewrite a Negated Statement (Lab 3, Task 3.h)

Rewrite ¬(∀x∃y((x ≠ 0) ∧ (xy ≠ 0)) ∨ ∃x∀y((x > y) ∧ (x + y ≠ 0))) so that no negation is outside a quantifier or logical connective.

Click to see the solution
  1. Apply De Morgan’s Law to the main disjunction (∨): The statement is of the form ¬(A ∨ B), which becomes ¬A ∧ ¬B.
    • ¬(∀x∃y((x ≠ 0) ∧ (xy ≠ 0))) ∧ ¬(∃x∀y((x > y) ∧ (x + y ≠ 0)))
  2. Rewrite the first part (¬A):
    • ¬∀x∃y(…) becomes ∃x∀y¬(…)
    • ∃x∀y¬((x ≠ 0) ∧ (xy ≠ 0)) becomes ∃x∀y(¬(x ≠ 0) ∨ ¬(xy ≠ 0)) by De Morgan’s law.
    • This simplifies to ∃x∀y((x = 0) ∨ (xy = 0)).
  3. Rewrite the second part (¬B):
    • ¬∃x∀y(…) becomes ∀x∃y¬(…)
    • ∀x∃y¬((x > y) ∧ (x + y ≠ 0)) becomes ∀x∃y(¬(x > y) ∨ ¬(x + y ≠ 0)) by De Morgan’s law.
    • This simplifies to ∀x∃y((x ≤ y) ∨ (x + y = 0)).
  4. Combine the rewritten parts with ∧:
Answer: The rewritten statement is (∃x∀y((x = 0) ∨ (xy = 0))) ∧ (∀x∃y((x ≤ y) ∨ (x + y = 0))).
4.21. Find Domains for Truth and Falsity (Lab 3, Task 4)

Find a common domain for x, y, and z for which ∀x∀y((x ≠ y) → ∀z((z = x) ∨ (z = y))) is true and another for which it is false.

Click to see the solution
  1. Analyze the statement: The statement says: “For any two different elements x and y in the domain, every element z in the domain must be either x or y.”
  2. Condition for Truth: This can only be true if the domain has at most two elements. If the domain has one element, the premise (x ≠ y) is always false, making the implication true. If the domain has two elements, the conclusion is true.
  3. Condition for Falsity: The statement will be false if the domain contains three or more distinct elements. In that case, we can pick two of them as x and y, and a third one as z, which will make the premise true and the conclusion false.

Answer:

  • Domain where it is True: Any set with two or fewer elements, e.g., {0, 1}.
  • Domain where it is False: Any set with three or more elements, e.g., {0, 1, 2}.
4.22. Find Domains for Truth and Falsity (Lab 3, Task 4.a)

Find a common domain for which the statement ∀x∀y(xy ≥ x) is true and another for which it is false.

Click to see the solution
  1. Analyze the statement: “For any two elements x and y from the domain, their product is greater than or equal to x.”
  2. Condition for Truth: This is true if y is always ≥ 1 (for positive x), or if y is ≤ 1 (for negative x), or if x is 0. A simple domain that works is one where y is always 1 or greater, and x is non-negative. For example, the set of integers greater than or equal to 1. Let’s test {1, 2, 3}: 1y ≥ 1 is true for y in {1,2,3}. 2y ≥ 2 is true. 3*y ≥ 3 is true.
  3. Condition for Falsity: The statement is false if we can find an x and y that violate it. For example, if x is positive and y is a fraction between 0 and 1, or if x is positive and y is negative.
    • Let the domain be the real numbers. Let x=2, y=0.5. Then xy = 1, and 1 ≥ 2 is false.

Answer:

  • Domain where it is True: The set of integers {1, 2, 3, …}.
  • Domain where it is False: The set of real numbers.
4.23. Find Domains for Truth and Falsity (Lab 3, Task 4.b)

Find a common domain for which the statement ∃x∀y(xy = y) is true and another for which it is false.

Click to see the solution
  1. Analyze the statement: “There exists an element x in the domain such that for every element y in the domain, xy = y.”
  2. Condition for Truth: This statement is true if the multiplicative identity element, which is 1, is in the domain. If we pick x=1, then 1*y = y is true for all y.
  3. Condition for Falsity: The statement is false if the number 1 is not in the domain.

Answer:

  • Domain where it is True: The set of integers.
  • Domain where it is False: The set of even integers {…, -4, -2, 0, 2, 4, …}.
4.24. Find Domains for Truth and Falsity (Lab 3, Task 4.c)

Find a common domain for which the statement ∀x∀y∃z(x + y + z = 0) is true and another for which it is false.

Click to see the solution
  1. Analyze the statement: “For any two elements x and y in the domain, there exists an element z (also in the domain) such that x + y + z = 0.”
  2. Condition for Truth: This is true if the domain is closed under addition and negation. For any x and y in the domain, z must equal -(x+y). If the sum -(x+y) is guaranteed to be in the domain, the statement is true. The set of integers or real numbers satisfies this.
  3. Condition for Falsity: The statement is false if we can find an x and y such that -(x+y) is not in the domain. The set of natural numbers (non-negative integers) is a good example.

Answer:

  • Domain where it is True: The set of real numbers.
  • Domain where it is False: The set of natural numbers {0, 1, 2, …} (e.g., if x=1, y=2, then z=-3, which is not in the domain).
4.25. Find Domains for Truth and Falsity (Lab 3, Task 4.d)

Find a common domain for which ∀x∀y∀z∃w((w ≠ x) ∧ (w ≠ y) ∧ (w ≠ z)) is true and another for which it is false.

Click to see the solution
  1. Analyze the statement: “For any three elements x, y, and z from the domain (not necessarily distinct), there exists another element w in the domain that is different from all of them.”
  2. Condition for Truth: This requires the domain to not be exhausted by picking any three elements. This means the domain must be infinite.
  3. Condition for Falsity: The statement is false if we can pick three elements that are all the elements in the domain. This means any finite domain with three or fewer elements will make it false.

Answer:

  • Domain where it is True: Any infinite set, such as the set of integers.
  • Domain where it is False: Any finite set, such as {1, 2, 3}.
4.26. Translate a Predicate Logic Statement (Tutorial 3, Task 1)

Let the domain consist of all students, and P(x) be “x has visited Innopolis”. Translate ∀xP(x) into English.

Click to see the solution
  1. Identify the quantifier: The symbol ∀x is the universal quantifier, which translates to “For all x,” “For every x,” or “Every x.”
  2. Identify the predicate: P(x) stands for “x has visited Innopolis”.
  3. Combine the parts: Replacing “x” with “student” from the domain, the statement reads: “For every student x, x has visited Innopolis.”
Answer: A more natural translation is: “Every student has visited Innopolis.”
4.27. Translate a Predicate Logic Statement (Tutorial 3, Task 2)

Let the domain consist of all students, and P(x) be “x has visited Innopolis”. Translate ¬∀xP(x) into English.

Click to see the solution
  1. Identify the main operator: The statement is a negation (¬) of a universally quantified statement (∀xP(x)).
  2. Translate the inner part: ∀xP(x) means “Every student has visited Innopolis.”
  3. Apply the negation: The negation ¬ translates to “It is not the case that…”.
  4. Combine the parts: “It is not the case that every student has visited Innopolis.”
  5. Find an equivalent statement: This is logically equivalent to saying that there is at least one student who has not visited Innopolis, which can be written as ∃x¬P(x).
Answer: A more natural translation is: “Not every student has visited Innopolis.” or “Some students have not visited Innopolis.”
4.28. Translate a Predicate Logic Statement (Tutorial 3, Task 3)

Let the domain consist of all students, and P(x) be “x has visited Innopolis”. Translate ∀x¬P(x) into English.

Click to see the solution
  1. Identify the quantifier: The symbol ∀x means “For every x.”
  2. Identify the predicate: The predicate is ¬P(x), which means “x has not visited Innopolis.”
  3. Combine the parts: “For every student x, x has not visited Innopolis.”
Answer: A more natural translation is: “No student has visited Innopolis.”
4.29. Translate a Predicate Logic Statement (Tutorial 3, Task 4)

Let the domain consist of all students, and P(x) be “x is smart”. Translate ∃xP(x) into English.

Click to see the solution
  1. Identify the quantifier: The symbol ∃x is the existential quantifier, which translates to “There exists an x,” “For some x,” or “There is at least one x.”
  2. Identify the predicate: P(x) stands for “x is smart.”
  3. Combine the parts: “There exists a student x such that x is smart.”
Answer: A more natural translation is: “Some student is smart.” or “There is at least one smart student.”
4.30. Translate a Predicate Logic Statement (Tutorial 3, Task 5)

Let the domain consist of all students, and P(x) be “x is smart”. Translate ¬∃xP(x) into English.

Click to see the solution
  1. Identify the main operator: The statement is a negation (¬) of an existentially quantified statement (∃xP(x)).
  2. Translate the inner part: ∃xP(x) means “Some student is smart.”
  3. Apply the negation: “It is not the case that some student is smart.”
  4. Find an equivalent statement: This is logically equivalent to saying that for all students, they are not smart (∀x¬P(x)).
Answer: A more natural translation is: “No student is smart.”
4.31. Translate a Predicate Logic Statement (Tutorial 3, Task 6)

Let the domain consist of all students, and P(x) be “x is smart”. Translate ∃x¬P(x) into English.

Click to see the solution
  1. Identify the quantifier: The symbol ∃x means “There exists an x.”
  2. Identify the predicate: The predicate is ¬P(x), which means “x is not smart.”
  3. Combine the parts: “There exists a student x such that x is not smart.”
Answer: A more natural translation is: “Some student is not smart.”
4.32. Translate a Predicate Logic Statement (Tutorial 3, Task 7)

Let the domain consist of all natural numbers, and let P(x) be “x is even” and R(x) be “x is prime”. Translate ∃x(P(x) ∧ R(x)) into English.

Click to see the solution
  1. Identify the quantifier: ∃x means “There exists some x.”
  2. Identify the predicates: P(x) is “x is even” and R(x) is “x is prime.” The conjunction P(x) ∧ R(x) means “x is even and x is prime.”
  3. Combine the parts: “There exists a natural number x such that x is even and x is prime.”
Answer: The translation is: “There exists an even prime number.” (This statement is true, as 2 is an even prime number).
4.33. Determine the Truth Value (Tutorial 3, Task 8)

Let the domain consist of all real numbers. Determine the truth value of ∃x(x = 0).

Click to see the solution
  1. Translate the statement: The statement says, “There exists a real number x such that x is equal to 0.”
  2. Analyze the statement: We need to check if the number 0 is included in the domain of real numbers.
  3. Conclusion: The number 0 is a real number. Therefore, an x exists that satisfies the condition.
Answer: The statement is True.
4.34. Determine the Truth Value (Tutorial 3, Task 9)

Let the domain consist of all real numbers. Determine the truth value of ∀x(x + 1 = x + 2).

Click to see the solution
  1. Translate the statement: The statement says, “For every real number x, x + 1 is equal to x + 2.”
  2. Analyze the statement: We can try to solve the equation x + 1 = x + 2. Subtracting x from both sides gives 1 = 2, which is a contradiction.
  3. Conclusion: There is no real number x for which this equation holds. Therefore, it is not true for “all” real numbers.
Answer: The statement is False.
4.35. Determine the Truth Value (Tutorial 3, Task 10)

Let the domain consist of all real numbers. Determine the truth value of ∀x∀y(x + y = y + x).

Click to see the solution
  1. Translate the statement: The statement says, “For any real numbers x and y, their sum is commutative.”
  2. Analyze the statement: This is the definition of the commutative property of addition for real numbers.
  3. Conclusion: This property holds true for all real numbers.
Answer: The statement is True.
4.36. Determine the Truth Value (Tutorial 3, Task 11)

Let the domain consist of integer numbers. Determine the truth value of ∃x∃y(x + y = xy).

Click to see the solution
  1. Translate the statement: “There exist integers x and y such that their sum equals their product.”
  2. Search for an example: We need to find at least one pair of integers (x, y) that satisfies the equation.
  3. Test values:
    • If we try x = 0, the equation becomes 0 + y = 0 * y, which simplifies to y = 0. So, the pair (0, 0) is a solution.
    • If we try x = 2, the equation becomes 2 + y = 2y, which simplifies to y = 2. So, the pair (2, 2) is another solution.
  4. Conclusion: Since we found at least one pair that satisfies the condition, the existential statement is true.
Answer: The statement is True.
4.37. Determine the Truth Value (Tutorial 3, Task 12)

Let the domain consist of all real numbers. Determine the truth value of ∀x∀y∀z(x + yz = xy + z).

Click to see the solution
  1. Translate the statement: “For all real numbers x, y, and z, the equation x + yz = xy + z holds.”
  2. Search for a counterexample: To prove a universal statement false, we only need to find one case where it doesn’t hold.
  3. Test values: Let x = 1, y = 2, and z = 3.
    • Left-hand side (LHS): x + yz = 1 + (2)(3) = 1 + 6 = 7.
    • Right-hand side (RHS): xy + z = (1)(2) + 3 = 2 + 3 = 5.
  4. Conclusion: Since 7 ≠ 5, we have found a counterexample.
Answer: The statement is False.
4.38. Rewrite a Negated Statement (Tutorial 3, Task 13)

Rewrite the statement ¬∃x(x ≠ 0) so that no negation is outside a quantifier.

Click to see the solution
  1. Apply the negation rule for quantifiers: The rule is ¬∃x P(x) ≡ ∀x ¬P(x).
  2. Substitute P(x): In this case, P(x) is the expression (x ≠ 0).
  3. Apply the rule: ¬∃x(x ≠ 0) becomes ∀x ¬(x ≠ 0).
  4. Simplify the inner expression: The negation of “not equal to” is “equal to”. So, ¬(x ≠ 0) is equivalent to (x = 0).
Answer: The rewritten statement is ∀x(x = 0).
4.39. Rewrite a Negated Statement (Tutorial 3, Task 14)

Rewrite the statement ¬∀x(x ≥ 0) so that no negation is outside a quantifier.

Click to see the solution
  1. Apply the negation rule for quantifiers: The rule is ¬∀x P(x) ≡ ∃x ¬P(x).
  2. Substitute P(x): In this case, P(x) is the expression (x ≥ 0).
  3. Apply the rule: ¬∀x(x ≥ 0) becomes ∃x ¬(x ≥ 0).
  4. Simplify the inner expression: The negation of “greater than or equal to” is “less than”. So, ¬(x ≥ 0) is equivalent to (x < 0).
Answer: The rewritten statement is ∃x(x < 0).
4.40. Rewrite a Negated Statement (Tutorial 3, Task 15)

Rewrite the statement ¬∀x∃y(x > y) so that no negation is outside a quantifier.

Click to see the solution
  1. Apply negation to the first quantifier: Using the rule ¬∀z P(z) ≡ ∃z ¬P(z), the statement becomes ∃x ¬(∃y(x > y)).
  2. Apply negation to the second quantifier: Using the rule ¬∃z Q(z) ≡ ∀z ¬Q(z), the inner part ¬(∃y(x > y)) becomes ∀y ¬(x > y).
  3. Combine the results: The full statement is ∃x ∀y ¬(x > y).
  4. Simplify the final predicate: The negation of “greater than” is “less than or equal to”. So, ¬(x > y) is equivalent to (x ≤ y).
Answer: The rewritten statement is ∃x ∀y (x ≤ y).
4.41. Rewrite a Negated Statement (Tutorial 3, Task 16)

Rewrite the statement ¬∀x((x > 0) ∧ (x < 100)) so that no negation is outside a quantifier or logical connective.

Click to see the solution
  1. Apply negation to the quantifier: Using the rule ¬∀x P(x) ≡ ∃x ¬P(x), the statement becomes ∃x ¬((x > 0) ∧ (x < 100)).
  2. Apply De Morgan’s Law: The rule is ¬(A ∧ B) ≡ (¬A ∨ ¬B). The expression becomes ∃x (¬(x > 0) ∨ ¬(x < 100)).
  3. Simplify the predicates: ¬(x > 0) is (x ≤ 0), and ¬(x < 100) is (x ≥ 100).
Answer: The rewritten statement is ∃x((x ≤ 0) ∨ (x ≥ 100)).
4.42. Rewrite a Negated Statement (Tutorial 3, Task 17)

Rewrite the statement ¬∃x¬P(x) so that no negation is outside a quantifier.

Click to see the solution
  1. Apply the negation rule for quantifiers: The rule is ¬∃y Q(y) ≡ ∀y ¬Q(y).
  2. Substitute Q(y): In this case, Q(x) is ¬P(x).
  3. Apply the rule: The statement becomes ∀x ¬(¬P(x)).
  4. Apply the double negation law: ¬(¬A) is equivalent to A.
Answer: The rewritten statement is ∀x P(x).
4.43. Rewrite a Negated Statement (Tutorial 3, Task 18)

Rewrite the statement ¬∀x(¬P(x) ∨ R(x)) so that no negation is outside a quantifier or logical connective.

Click to see the solution
  1. Apply negation to the quantifier: Using the rule ¬∀x Q(x) ≡ ∃x ¬Q(x), the statement becomes ∃x ¬(¬P(x) ∨ R(x)).
  2. Apply De Morgan’s Law: The rule is ¬(A ∨ B) ≡ (¬A ∧ ¬B). The expression becomes ∃x (¬(¬P(x)) ∧ ¬R(x)).
  3. Apply the double negation law: ¬(¬P(x)) becomes P(x).
Answer: The rewritten statement is ∃x(P(x) ∧ ¬R(x)).
4.44. Find Domains for Truth and Falsity (Tutorial 3, Task 19)

Find a common domain for the variable x for which the statement ∃x(x = 0) is true and another domain for which it is false.

Click to see the solution
  1. Analyze the condition for truth: For the statement to be true, the domain must contain the element 0.
  2. Analyze the condition for falsity: For the statement to be false, the domain must not contain the element 0.
  3. Provide examples:
    • True: The set of all integers, { -1, 0, 1 }, the set of real numbers.
    • False: The set of positive integers, {1, 2, 3, 4}, the set of negative integers.

Answer:

  • Domain where it is True: The set of real numbers (ℝ).
  • Domain where it is False: The set of positive integers (ℤ⁺).
4.45. Find Domains for Truth and Falsity (Tutorial 3, Task 20)

Find a common domain for the variable x for which the statement ∀x(x > 0) is true and another domain for which it is false.

Click to see the solution
  1. Analyze the condition for truth: For the statement to be true, every element in the domain must be greater than 0.
  2. Analyze the condition for falsity: For the statement to be false, the domain must contain at least one element that is less than or equal to 0.
  3. Provide examples:
    • True: The set of positive integers {1, 2, 3, …}, the set of positive real numbers.
    • False: The set of all integers, the set of real numbers (since it contains 0 and negative numbers).

Answer:

  • Domain where it is True: The set of positive real numbers (ℝ⁺).
  • Domain where it is False: The set of all real numbers (ℝ).
4.46. Find Domains for Truth and Falsity (Tutorial 3, Task 21)

Find a common domain for the variables x and y for which the statement ∀x∀y(xy > 0) is true and another domain for which it is false.

Click to see the solution
  1. Analyze the condition for truth: For the statement to be true, the product of any two elements (including an element with itself) from the domain must be positive. This works if all elements are positive or if all elements are negative.
  2. Analyze the condition for falsity: For the statement to be false, there must be at least one pair of elements whose product is not positive (i.e., is zero or negative). This happens if the domain contains 0, or if it contains both positive and negative numbers.
  3. Provide examples:
    • True: The set of positive integers {1, 2, 3, …}.
    • False: The set of all integers (e.g., 2 * -3 = -6; 5 * 0 = 0).

Answer:

  • Domain where it is True: The set of positive integers (ℤ⁺).
  • Domain where it is False: The set of all integers (ℤ).
4.47. Find Domains for Truth and Falsity (Tutorial 3, Task 22)

Find a common domain for the variables x and y for which the statement ∃x∃y(x + y > 0) is true and another domain for which it is false.

Click to see the solution
  1. Analyze the condition for truth: For the statement to be true, there must exist at least one pair of elements in the domain whose sum is positive.
  2. Analyze the condition for falsity: For the statement to be false, the sum of any two elements from the domain must be less than or equal to 0.
  3. Provide examples:
    • True: The set of all integers (e.g., 2 + 3 = 5 > 0).
    • False: The set of negative integers {-1, -2, -3, …} (the sum of any two is always negative).

Answer:

  • Domain where it is True: The set of integers (ℤ).
  • Domain where it is False: The set of negative integers (ℤ⁻).
4.48. Find Domains for Truth and Falsity (Tutorial 3, Task 23)

Find a common domain for the variables x and y for which the statement ∃x∀y(x = y) is true and another domain for which it is false.

Click to see the solution
  1. Analyze the condition for truth: The statement says “there exists an element x such that every element y is equal to x”. This can only be true if all elements in the domain are the same, which means the domain has only one element.
  2. Analyze the condition for falsity: For the statement to be false, the domain must contain at least two different elements.
  3. Provide examples:
    • True: Any set with a single element, for example, {5}.
    • False: Any set with two or more elements, for example, {5, 6}.

Answer:

  • Domain where it is True: The set {1}.
  • Domain where it is False: The set of integers (ℤ).
4.49. Find Domains for Truth and Falsity (Tutorial 3, Task 24)

Find a common domain for the variables x and y for which the statement ∀x((x ≠ 0) → ∃y(xy = 1)) is true and another domain for which it is false.

Click to see the solution
  1. Analyze the condition for truth: The statement says “for any non-zero element x, there exists an element y such that their product is 1”. This means that every non-zero element must have a multiplicative inverse within the domain. Such a set is called a field.
  2. Analyze the condition for falsity: For the statement to be false, there must be at least one non-zero element that does not have a multiplicative inverse in the domain.
  3. Provide examples:
    • True: The set of rational numbers (ℚ) or the set of real numbers (ℝ). For any non-zero rational x, its inverse 1/x is also rational.
    • False: The set of integers (ℤ). For x=2, its inverse y=1/2 is not an integer.

Answer:

  • Domain where it is True: The set of real numbers (ℝ).
  • Domain where it is False: The set of integers (ℤ).
4.50. Find Domains for Truth and Falsity (Tutorial 3, Task 25)

Find a common domain for x, y, and z for which ∀x∀y((x ≠ y) → ∀z((z = x) ∨ (z = y))) is true and another for which it is false.

Click to see the solution
  1. Analyze the condition for truth: The statement says “for any two different elements x and y, every element z in the domain is either x or y”. This implies that the domain cannot have more than two elements. If it has one element, the premise (x ≠ y) is always false, making the implication vacuously true. If it has two elements, the conclusion is true.
  2. Analyze the condition for falsity: For the statement to be false, there must be at least three elements in the domain.
  3. Provide examples:
    • True: A set with exactly two elements, like {0, 1}.
    • False: A set with three or more elements, like {0, 1, 2}. We can pick x=0, y=1. Then for z=2, z is not equal to x and z is not equal to y.

Answer:

  • Domain where it is True: The set {a, b}.
  • Domain where it is False: The set of integers (ℤ).